Nguyễn Hữu Vinh là con trai út của ông Nguyễn Hữu Khiếu (1915-2005), một lão thành cách mạng, từng là ủy viên trung ương Đảng CSVN trong 2 khóa, nguyên Bí thư Tỉnh ủy Thanh Hóa, Bộ trưởng Bộ Lao động Việt Nam, đại sứ Việt Nam tại Liên Xô.[5] Ông Vinh có hộ khẩu thường trú tại số phường Trung Tự, quận Đống Đa, TP. Hà Nội.

Nguyễn Hữu Vinh học cấp 3 tại trường Trung học phổ thông Chu Văn An, Hà Nội. Sau đó ông theo học Đại học An ninh nay là Học viện An ninh nhân dân Hà Nội. Sau khi hoàn thành khóa học, ông được ngành Công an trao quyết định là sĩ quan Công an.

Được ít năm, ông xin chuyển khỏi ngành Công an, sang làm việc ở Ban Việt kiều Trung ương.

Sau khi bỏ việc nhà nước vào giữa thập niên 1990, Nguyễn Hữu Vinh học luật. Năm 2000, Nguyễn Hữu Vinh thành lập Công ty TNHH Điều tra và Bảo vệ - VPI, là công ty thám tử tư đầu tiên ở Việt Nam.[6]

Ông có gia đình, vợ là bà Lê Thị Minh Hà và có con.